package graph.question;

import graph.GraphNode;
import graph.graphtype.NoDirectGraph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-11 16:31:54
 */
// 节点之间最短的路径 BFS

public class NodeMinLengthPath {

    public List<Integer> minPath(NoDirectGraph g, int p1, int p2){

        int[] visited = new int[g.table.length];
        // 记录到 i 节点的前一个节点为 path[i]
        // 实际上path 数组包含了 该节点 到其他所有节点的 最短路径
        int[] path = new int[g.table.length];
        int tempId;

        Queue<GraphNode> stack = new LinkedList<>();
        stack.add(g.table[p1]);
        path[p1] = p1;

        while (!stack.isEmpty()){
            GraphNode tempNode = stack.poll();
            tempId = tempNode.id;
            visited[tempId] = 1;
            while (tempNode.next != null){
                if (visited[tempNode.next.id] != 1){
                    stack.add(tempNode.next.edgeNode);
                    path[tempNode.next.id] = tempId;
                    visited[tempNode.next.id] = 1;
                }
                tempNode = tempNode.next;
            }
        }


        // 根据path数组得到最短路径
        List<Integer> result = new ArrayList<>();
        tempId = p2;
        while (tempId != path[tempId]){
            result.add(0, tempId);
            tempId = path[tempId];
        }
        result.add(0, p1);
        return result;

    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {0, 4}, {1, 0}, {1, 3}, {2, 0}, {2, 3}, {2, 4}, {3, 1}, {3, 2}, {3, 4}, {4, 0}, {4, 2}, {4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};

        //int[][] edges = new int[][]{{0, 2}, {0, 5}, {2, 0}, {2, 1}, {1, 2}, {1, 4}, {4, 1}, {4, 6}, {6, 4}, {6, 3}, {3, 5}, {3, 6}, {5, 0}, {5, 3}};
        // int[] data = new int[]{1, 2, 3, 4, 5, 6, 7};

        NoDirectGraph g = new NoDirectGraph(data.length, data);
        g.generateGraph(edges);

        List<Integer> result = new NodeMinLengthPath().minPath(g, 1, 2);

        System.out.println("result = " + result);
    }


}
